package com.example.dynamicprogramming41.practice;

/**
 * @description 我们有 3 种不同的硬币，1 元、3 元、5 元，我们要支付 9 元，最少需要 几 个硬币
 * @auther lijiewei
 * @date 2022/4/14 15:47
 */
public class FlashBackPractice2 {

    private int[] coin = {1, 3, 5};
    private int money = 9;
    //存的值是指向当前的下标
    private int[] mem = new int[money];


    public void minCoin(int index, int curMoney) {
        if (curMoney == money) {
            for (int i = 0; i < mem.length; i++) {
                if (mem[i]>0) {
                    System.out.print(mem[i]+" ");
                }
            }
            System.out.println();
            return ;
        }
        for (int i = 0; i < coin.length; i++) {
            if (curMoney+coin[i] <= money) {
                mem[index] = coin[i];
                minCoin(index+1, curMoney+coin[i]);
                mem[index] = 0;
            }
        }
    }

    public void print(int index) {
        while(mem[index]>=0) {
            int preIndex = mem[index];
            System.out.print(index-preIndex+" ");
            index = preIndex;
            if (index == 0) {
                System.out.println();
                return;
            }
        }

    }
}
